package bfs;
import com.sun.xml.internal.bind.v2.TODO;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;



class Solution {
    boolean[][] visited;
    int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int numIslands(char[][] grid) {
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    bfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    //将这片岛屿上的所有陆地都访问到
    public void bfs(char[][] grid, int y, int x) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{y, x});
        visited[y][x] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int m = cur[0];
            int n = cur[1];
            for (int i = 0; i < 4; i++) {
                int nexty = m + move[i][0];
                int nextx = n + move[i][1];
                if (nextx < 0 || nexty == grid.length || nexty < 0 || nextx == grid[0].length) continue;
                if (!visited[nexty][nextx] && grid[nexty][nextx] == '1') {
                    queue.offer(new int[]{nexty, nextx});
                    visited[nexty][nextx] = true; //只要加入队列就标记为访问
                }
            }
        }
    }
}

public class Class200 {

//    public int numIslands(char[][] grid) {
//        int res = 0; //记录找到的岛屿数量
//        for(int i = 0;i < grid.length;i++){
//            for(int j = 0;j < grid[0].length;j++){
//                //找到“1”，res加一，同时淹没这个岛
//                if(grid[i][j] == '1'){
//                    res++;
//                    dfs(grid,i,j);
//                }
//            }
//        }
//        return res;
//    }


//    //使用DFS“淹没”岛屿
//    public void dfs(char[][] grid, int i, int j){
//        //搜索边界：索引越界或遍历到了"0"
//        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
//        //将这块土地标记为"0"
//        grid[i][j] = '0';
//        //根据"每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成"，对上下左右的相邻顶点进行dfs



    //TODO:2023/9/21 这样子的形式遇到 为0的字符 就终止向下递归了  不会遍历到不属于当前陆地组成部分的陆地
//    TODO:上下左右淹没所有岛屿
//        dfs(grid,i - 1,j);  向左淹没所有岛屿
//        dfs(grid,i + 1,j);  向右淹没所有岛屿
//        dfs(grid,i,j + 1);  向上淹没所有岛屿
//        dfs(grid,i,j - 1);  向下淹没所有岛屿
//    }

boolean[][]  record;

    public int numIslands(char[][] grid) {
        record = new boolean[grid.length][grid[0].length];
        int res=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(!record[i][j]&&grid[i][j]=='1'){
                    res++;
                    bfs(i,j,grid);
                }
            }
        }
        return res;
    }


    public void bfs (int x,int y,char[][]grid) {
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Deque<int[]> deque = new LinkedList<>();
        deque.add(new int[]{x, y});
        record[x][y] = true;

        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            int curX = cur[0];
            int curY = cur[1];

            //TODO:2023/9/21  这样子广度优先遍历  以当前节点为中心 环绕四周的节点都放入到队列中  画图刚好也不能把不属于当前陆地的节点放进去

            for (int i = 0; i < 4; i++) {
                int nowX = curX + dir[i][0];
                int nowY = curY + dir[i][1];
//                if (nowX > 0 && nowX < grid.length && nowY > 0 && nowY < grid[0].length && !record[nowX][nowY]&&grid[nowX][nowY]=='1') {
//                    record[nowX][nowY] = true;
//                    deque.add(new int[]{nowX, nowY});
//                }
                if (nowX < 0 || nowX == grid.length || nowY < 0 || nowY == grid[0].length) continue;
                if (!record[nowX][nowY] && grid[nowX][nowY] == '1') {
                    deque.offer(new int[]{nowX, nowY});
                    record[nowX][nowY] = true; //只要加入队列就标记为访问
                }
            }



        }

    }


            public static void main (String[]args){
                Class200 class200 = new Class200();
                char[][] grid = {
                        {'1', '1', '0', '0', '0'},
                        {'1', '1', '0', '0', '0'},
                        {'0', '0', '1', '0', '0'},
                        {'0', '0', '0', '1', '1'}
                };
                int i = class200.numIslands(grid);
                System.out.println(i);
            }
        }

